package org.cainiao.algorithm.temp;

import java.util.*;

/**
 * <br />
 * <p>
 * Author: Cai Niao(wdhlzd@163.com)<br />
 */
public class TempTest3 {

    public static void main(String[] args) {
        String[][] board = {
            {"x", "x", "x", "x"},
            {"x", "o", "o", "x"},
            {"x", "x", "o", "x"},
            {"x", "o", "x", "x"}};
        System.out.println(Arrays.deepToString(test1(board)));

        System.out.println(test2(new int[]{2, 1, 5, 6, 2, 3}));

        System.out.println(test3(10, 11)); // false
        System.out.println(test3(10, 0)); // true
        System.out.println(test3(10, 1)); // true
    }

    private static boolean test3(int maxChoosableInteger, int desiredTotal) {
        return isFirstWin(1, maxChoosableInteger, desiredTotal, new HashSet<>());
    }

    private static boolean isFirstWin(int min, int max, int desiredTotal, Set<Integer> selected) {
        for (int number = min; number <= max; number++) {
            if (!selected.contains(number)) {
                if (number >= desiredTotal) {
                    return true;
                }
                selected.add(number);
                boolean isSecondWin = isFirstWin(min, max, desiredTotal - number, selected);
                selected.remove(number);
                if (!isSecondWin) {
                    return true;
                }
            }
        }
        return false;
    }

    private static int test2(int[] heights) {
        Stack<List<Integer>> stack = new Stack<>();
        int length = heights.length;
        int[][] records = new int[length][2];
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek().get(0)]) {
                popAndRecord(records, stack, i);
            }
            if (!stack.isEmpty() && heights[i] == heights[stack.peek().get(0)]) {
                stack.peek().add(i);
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(i);
                stack.push(temp);
            }
        }
        while (!stack.isEmpty()) {
            popAndRecord(records, stack, -1);
        }
        int max = 0;
        for (int i = 0; i < records.length; i++) {
            int[] record = records[i];
            int leftIndex = record[0] < 0 ? i : (record[0] + 1);
            int rightIndex = record[1] < 0 ? i : (record[1] - 1);
            int maxOfI = heights[i] * (rightIndex - leftIndex + 1);
            if (maxOfI > max) {
                max = maxOfI;
            }
        }
        return max;
    }

    private static void popAndRecord(int[][] records, Stack<List<Integer>> stack, int rightLessIndex) {
        List<Integer> topIndexes = stack.pop();
        for (int topIndex : topIndexes) {
            records[topIndex][0] = stack.isEmpty() ? -1 : stack.peek().get(0);
            records[topIndex][1] = rightLessIndex;
        }
    }

    private static String[][] test1(String[][] board) {
        int height = board.length;
        if (height < 1) {
            return new String[][]{{}};
        }
        int width = board[0].length;
        String[][] result = new String[height][width];
        for (int rowIndex = 0; rowIndex < height; rowIndex++) {
            String[] columns = board[rowIndex];
            for (int columnIndex = 0; columnIndex < width; columnIndex++) {
                String element = columns[columnIndex];
                if ("o".equals(element) && (rowIndex == 0 || rowIndex == height - 1
                    || columnIndex == 0 || columnIndex == width - 1)) {

                    result[rowIndex][columnIndex] = "o";
                } else {
                    result[rowIndex][columnIndex] = "x";
                }
            }
        }
        return result;
    }
}
